#index range from 0...n-1
def left(i):
    return 2*i+1
def right(i):
    return 2*i+2
def parent(i):
    return (i-1)//2
def max_heapify(A,i): #小的元素下沉
    global heapsize
    L=left(i)
    R=right(i)
    largest=i
    if L<heapsize and A[L]>A[i]:
        largest=L
    if R<heapsize and A[R]>A[largest]:
        largest=R
    if largest!=i:
        A[i],A[largest]=A[largest],A[i]
        max_heapify(A,largest)
def build_maxheap(A):
    global heapsize
    for i in range((heapsize-1)/2,-1,-1):
        max_heapify(A,i)
def heap_maximum(A):
    return A[0]
def heap_extract_max(A):
    global heapsize
    if heapsize==0:
        raise Exception('heap underflow')
    max=A[0]
    A[0]=A[heapsize-1]
    heapsize-=1
    max_heapify(A,0)
    return max
def heap_increase_key(A,i,key):
    if key<A[i]:
        raise Exception('new key is smaller than current key')
    while i>0 and A[parent(i)]<key:
        A[i]=A[parent(i)]
        i=parent(i)
    A[i]=key
def maxheap_insert(A,key):
    global heapsize
    heapsize+=1
    A[heapsize-1]=key-1
    heap_increase_key(A,heapsize-1,key)
def heap_delete(A,i):
    global heapsize
    if i>heapsize-1:
        raise Exception('i is out of heap')
    key=A[i]
    A[i]=A[heapsize-1]
    heapsize-=1
    max_heapify(A,i)
    return key

if __name__=='__main__':
    A=[2,3,5,1,7,8,9,0,6]
    heapsize=len(A)    
    print 'A:', A, 'size:', heapsize
    build_maxheap(A)
    print 'build maxheap:', A
    print 'heap_maximum:', heap_maximum(A)
    print 'extract max:', heap_extract_max(A)
    print 'A:', A, 'size:', heapsize
    heap_increase_key(A,3,100)
    print 'increased key:', A
    maxheap_insert(A,77)
    print 'inserted 77:', A
    print 'delete 6th ele:', heap_delete(A,5)
    print 'A:', A, 'size:', heapsize
